package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/30 21:25
 */
public class M1710 {

    // 摩尔投票, 不一定有, 所以遍历两边
    public static int majorityElement(int[] nums) {
        int N;
        if (nums == null || (N = nums.length) == 0) return -1;
        int candidate = nums[0], count = 1;
        for (int i = 1; i < N; i++) {
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            } else {
                count = candidate == nums[i] ? count + 1 : count - 1;
            }
        }
        count = 0;      // 在遍历一边统计候选人的出现次数, 因为有可能没有出现半数以上的元素
        for (int i = 0; i < N; i++) {
            count = nums[i] == candidate ? count + 1 : count;
        }
        return (count << 2 >= N )? candidate : -1;
    }

}
